#include <algorithm>
#include <forward_list>
#include <vector>
#include <list>
#include <iostream>
#include <climits>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <utility>

using namespace std;

unsigned long long rdtsc(){
      //en edx:eax esta el valor del tsc
        asm volatile("rdtsc");
}   

int particionK  = 0;
vector< vector<int> > grafoAdj;
int V = 0;

typedef pair<int, pair <forward_list<int>::iterator, int> > tupla_type;

struct comp{
  bool operator()(tupla_type const& lhs, tupla_type const& rhs){
    return lhs.first > rhs.first;
  }
};

typedef struct {
        //particiones creadas
        vector< list<int> > particiones;
        int p_count;
        int peso_total;
} result;

void putEje(int x,int y, int w){
        //if (x> y) swap(x,y);
        //cout << "put eje "<<x << " "<< y << " -- " << ( x*y)+y << " en "<< w << "\n";
        //grafoAdj[ ( x*y)+y] = w;
        grafoAdj[x][y]=w;
        grafoAdj[y][x]=w;
}

int getEje(int x,int y){
        //if (x> y) swap(x,y);
        //cout << "get eje " <<x << " "<< y << " -- " << ( x*y)+y << " en "<< grafoAdj[( x*y)+y] << "\n";
        //return grafoAdj[( x*V)+y];
        return grafoAdj[x][y];
}
void debugResult(result *r){

        cout << "p_count : " << r->p_count ;
        cout << " peso_total :" << r->peso_total << "\n";

        int p=0;
        for (auto it= r->particiones.begin();it!= r->particiones.end(); ++it){
                cout << "particion : " <<  p  << " = ";

                for (auto t=it->begin(); t != it->end(); ++t){                  
                        cout << " " << *t ;                            
                       
                }
                cout <<  "\n";          
                p++;
        }                      
        cout << "\n";
}
int getPartition(result &r, int v){
       
        int found = -1;
        list<int>::iterator it;
        int currentP = 0;
       
        for (auto part= r.particiones.begin();part!= r.particiones.end(); ++part){

                 it = find (part->begin(), part->end(), v);
                if (it != part->end()){
                        found = currentP;
                }
                currentP ++;
        }
        return found;
}

int calcularReemplazo(result & r, int p,int ady1, int ady2 , int ady2part=-1){
       
        int diff  = 0;  
        list<int>::iterator it,it2;
        if(ady2part < 0 )
                ady2part = getPartition(r,ady2);

        int w;
        for( it = r.particiones[p].begin() ; it != r.particiones[p].end(); ++it ){              
                 if ( (*it) != ady1 ){                                          
                        w = getEje(*it,ady1);

                        if (w > 0) diff -= w;
                        if (ady2 >= 0){
                                w = getEje(ady2,*it);
                                if (w>0) diff += w;                                                    
                        }
                }                      
        }
//      cout << "--" << r.particiones.size()<< "\n";
//      cout << "--" << r.particiones[ady2part].size() << "\n";
        for( it2 = (r.particiones[ady2part]).begin() ; it2 != (r.particiones[ady2part]).end();++it2){
//              cout << " -a " << ady2part << " - "<< r.particiones[ady2part].size();
//              cout  << "  "<< *it2 << "\n";
                if ( (*it2) != ady2  ){
                        if( ady2 >= 0){
                                w = getEje(ady2,*it2);
                                if (w > 0) diff -= w;
                        }

                        w = getEje(ady1,*it2    );
                        if (w>0) diff += w;                    
                }                      
        }
//      cout << " -b\n";
        return diff;
}

void actualizarPeso(result & r, int particion, int v){//actualiza el atributo "r.peso_total" como resultado de colocar v en la particion indicada.
	//cout << "comienzo a act peso en la part: " << particion << " del nodo:  " << v <<endl;
        if  (r.peso_total == INT_MAX){
                r.peso_total = 0;
			}
       
        int p;
        for(auto it = r.particiones[particion].begin() ; it != r.particiones[particion].end();++it){
                if (v != *it){

                        p = getEje(v,*it);
						//cout << "peso "<< p << " de "<< v << " : "<< *it <<"\n";
                        r.peso_total += p;
                }

                       
        }
     //cout << "sale de actualizar peso "<< r.peso_total << "\n" ;
}

int diferencialPeso(result & r, int particion, int v){//devuelve el peso que se adicionaria si se agrega el nodo v en particion.
	    int p = 0;
        for(auto it = r.particiones[particion].begin() ; it != r.particiones[particion].end();++it){
                if (v != *it){

                        p += getEje(v,*it);
						
                }
       }
return p;
}

//reemplazo aplicable a una solucion
typedef struct {
        int v;
        int vpart;
        int adjin;
        int adjout;
        int outpart;
        int gain;
} reemplazo;

bool reemplazoSort(reemplazo a, reemplazo b){return (a.gain < b.gain);}

void aplicarCambio(result & r, reemplazo rem){
       
        if (rem.adjout >= 0 ){
                r.particiones[rem.vpart].remove(rem.adjout);            
        }
        r.particiones[rem.vpart].push_front(rem.adjin);
        r.particiones[rem.outpart].remove(rem.adjin);
        if (rem.adjout >= 0 ){
                r.particiones[rem.outpart].push_front(rem.adjout);
        }
        r.peso_total += rem.gain;
}

void busquedaLocal(result  &r,int start = -1){
        int p=0,p2 = 0;
        //para cada particion
        int ady1W, ady2W = -1;
        int ady2part;
        int diff;
        list<reemplazo> vecindad;
        reemplazo* rem;
        //cout << "++++++++++++++++\n";
        for (auto part= r.particiones.begin();part!= r.particiones.end(); ++part){
                //para cada vertice de la particion
                for (auto v=part->begin(); v != part->end(); ++v){                                              
                        // para cada adyacente a v dentro de la particion
                        // busco otro adyacente afuera de la partcion
                        for (int ady1=0 ; ady1< V; ady1++){

                                ady1W = getEje(*v,ady1);
                                if (ady1 > *v && ady1W > 0 && p == getPartition(r,ady1) ){
                                        //son adyacentes y estan en la misma particion
                                       
                                        //busco un adyacente afuera de part
                                        for (int ady2 = 0; ady2 < V; ady2++ ){

                                                ady2W = getEje(*v,ady2);
                                                ady2part = getPartition(r,ady2);
                                                if (*v != ady2 && ady2W > 0 && p != ady2part ){
                                        //              cout <<  "encontre v: " << *v;                                                  
                                        //              cout << " ady1 : " << ady1;
                                        //              cout << " ady2 : " << ady2 ;
                                        //              cout << " diff : " << calcularReemplazo(r, p,ady1,ady2,ady2part) << "\n" ;

                                                        diff = calcularReemplazo(r, p,ady1,ady2);
                                        //              cout << "pincha \n";
                                                        if (diff < 0){
                                                                rem = new reemplazo;
                                                                rem->v = *v;
                                                                rem->vpart = p;
                                                                rem->adjin = ady2;
                                                                rem->adjout =  ady1;
                                                                rem->outpart = ady2part ;
                                                                rem->gain = diff;                                                      
                                                                vecindad.push_front(*rem);                                                              
                                                        }
                                                }
                                        }
                                        p2 =0;
                                        //cout << "paso";
                                        for (auto part2 = r.particiones.begin(); part2!= r.particiones.end(); ++part2){
                                        //      cout << "entro" ;
                                                if (p != p2){
                                                        diff = calcularReemplazo(r, p,ady1,-1,p2);
                                        //              cout << "encontre reemplazo ";
                                        //              cout << " cambio ady1 "<< ady1 << " de  p: "<< p;
                                        //              cout << " a "<< p2 << "\n";
                                        //              cout << " diff " << diff << "\n";
                                                        if (diff <0){
                                                                rem = new reemplazo;
                                                                rem->v = -1;
                                                                rem->vpart = p2;
                                                                rem->adjin = ady1;
                                                                rem->adjout =  -1;
                                                                rem->outpart = p ;
                                                                rem->gain = diff;                                                      
                                                                vecindad.push_front(*rem);                                                                                                                      
                                                        }
                                                }
                                                p2 ++ ;                                        
                                        }

                                }      
                        }
                }
                p++;
        }                      
        if (vecindad.size()>0){
                vecindad.sort(reemplazoSort);
                aplicarCambio(r,vecindad.front());
                busquedaLocal(r,start);
        }
        // for p particion en r
        //      for v vertice en p
        //              buscar 1 vertice adyacente en p y otro en otra particion
        //          tal que el eje dentro de p sea mayor que el eje fuera de p
}

void particion(result  &r, forward_list<int> disponibles){

    forward_list<int> dispParam;
    forward_list<int>::iterator minI;
    result resParam, minRes;
    vector < tupla_type > alfas;
    alfas.resize(0);
    minRes.peso_total = INT_MAX;
	//cout << "---------------------- \n";
	int peso_aux = INT_MAX;
	int part_aux = 0;
	int alfa;
	int cota;
	int ll;
	forward_list<int>::iterator it_aux;
    int d_size = distance(begin(disponibles), end(disponibles));
    //cout << "entro a particion con " << d_size << " disponibles \n" ;
	for(auto it = disponibles.begin(); it != disponibles.end();++it){
		dispParam = disponibles;
		dispParam.remove(*it);
		it_aux = it;
		
		//no es necesario que obligatoriamente ubique el vertice en una particion nueva
		if (r.p_count > 0 ){
			/*para cada particion creada
			agrego el vertice a la particion y calculo el peso peso_total
			si es mejor que el existente actualizo peso */			
			for(int i=0 ; i< r.p_count; i++){
				//resParam  = r;
				//resParam.particiones[i].push_front(*it);
				//actualizarPeso(resParam,i,*it);
				ll= diferencialPeso(r,i,*it);
				if (ll < peso_aux){
					peso_aux = ll;
					part_aux = i;
					}
				
				/*if (resParam.peso_total < minRes.peso_total){
						minRes = resParam;
						minI = it;
					
				}*/
			}
		}
		
		// si aun se pueden agregar particiones pruebo agregando 
		//una particion
		if ( particionK > r.p_count ){			
			//resParam  = r;
			//resParam.particiones[resParam.p_count].push_front(*it);
			//resParam.p_count += 1;
 			//actualizarPeso(resParam,resParam.p_count-1,*it);
 			ll=diferencialPeso(r,r.p_count,*it);
			
			if (ll < peso_aux){
					peso_aux = ll;
					part_aux = r.p_count;
				}

			/*if (resParam.peso_total < minRes.peso_total){
	//			cout << "actualizo "<< resParam.peso_total << "\n";
				minRes = resParam;				
	//			cout << *it <<" min I \n";
				minI = it;
			}*/
		}
		
		alfas.push_back(make_pair(peso_aux,make_pair(it_aux,part_aux)));
		peso_aux = INT_MAX;
		part_aux = 0;
		
	}

	//al salir del for tengo guardado en el vector para cada nodo donde me  cada uno tengo que escoger un valor aleatoriamente
	make_heap(alfas.begin(),alfas.end(),comp());
	
	tupla_type a;
	/*cout << "a continuacion se imprime el arreglo de alfas" << endl;
 	for (int i=0 ; i < alfas.size(); i++){
		cout << "elemento: " <<i << "del arreglo:" << endl; 
		a = alfas[i];
		cout << "el peso es: " << a.first << " la particion es: " << a.second.second << "  el nodo es " << *a.second.first << endl;
		
	}
	cout << "+++++++++++++++++++++++"<< endl;
	*/
	//el arreglo alfas contiene a las posibles k posiciones de los k nodos (posiciones de peso minimo para cada nodo) de manera ascendente
	alfa = alfas[0].first; //alfa contiene el peso minimo que se va a agregar en esta iteracion
	int alfa2 = alfa;
	cota = (alfa/2);
	cota = cota + alfa;		//para entrar en la lista de candidatos no tienen que superar mas del 25% al candidato optimo
	int j= 0;
	bool cont = true;
	while(alfa2 <= cota && j<alfas.size()){
		//cout << "entre al while" << endl;
		j++;
		alfa2 = alfas[j].first;
		
		//si ya pasaron todos los mejores resultados
		/*if (alfa2 > alfa){
			if(j>4){
			cont = false;
			}
		}*/
		
	}
	//cout << "sali del while" << endl;
	//ahora se escoge un numero aleatorio entre 0 y j
	alfa2 = rand() % j;
	a = alfas[alfa2];
	
	r.particiones[a.second.second].push_front(*a.second.first);
	if (!(r.p_count > a.second.second)){
		r.p_count++;
	}
 	actualizarPeso(r,a.second.second,*a.second.first);
 	
 	//r = minRes;
	//cout << "resultados parciales:" << endl;
	//debugResult(&r);
	if (d_size > 1){
		disponibles.remove(*a.second.first);
	//	cout << "remuevo " << *minI << "\n";
	//	debugResult(&r);		
		particion(r, disponibles);
	}

}

/*
- sea R una solucion con I particiones  
- sea C la  lista de vertices todabia no ubicados en alguna particion
  para cada uno de estos vertices tomo uno y lo retiro de la lista

        - si puedo agregar una particion mas agrego una particion
          solo con el vertice que retire y llamo recursivamente

        - si puedo no agregar una particion agrego el vertice que retire
           a cada una de las particiones para luego llamar recursivamente
   
    - si alguna de las soluciones que evalue es mejor que la mejor conocida
    me quedo con esa solucion.

*/

void printResult(result *r){

        int p = 0;
        for (int i=0; i< V ; i++){
                p = 0;
                for (auto it= r->particiones.begin();it!= r->particiones.end(); ++it){
                       
                        for (auto t=it->begin(); t != it->end(); ++t){
                                if ( *t == i ){
                                        cout <<  p << " "  ;
                                        break;
                                }
                        }
                       
                        p++;
                }                      
        }
        cout << "\n";
}
void grasp(result  &r, forward_list<int> d){
        //cout << "entro a grasp \n";
        forward_list<int> d1 = d;
        result  raux,best;
       
        int first = 1;
        int bestResult =INT_MAX;
        int resultCount = 0;
        //particion(r,d);
        while (true){          
                //random_shuffle ( shu.begin(), shu.end() );
                //for (int i=0 ; i< shu.size(); i++){
                  //      d1.push_front(shu[i]);
                //}      
                raux = r;
                                
                //cout<< "entro al goloso \n";
                //goloso aleatorizado
                particion(raux,d1);
                
                //debugResult(&raux);  
                //cout<< "entro al local \n";  
                busquedaLocal(raux);
                //cout<< "salgo del local \n";
                //debugResult(&best);    
                //cout << "test \n" ;
                if ( bestResult  > raux.peso_total){
                        //cout << "aaaa\n";
                        bestResult = raux.peso_total;
                        best =  raux;
                        resultCount = 0;
                }else{
                        //cout << "bbb\n";
                        if (resultCount > 10){
                                break;
                        }else{
                                resultCount ++;
                        }
                }
        }
       //cout << "resultado final:" << endl;
       //debugResult(&best);          
                       

}


//*************************************************************************************************************

void particion2(result  &r, forward_list<int> disponibles){

    forward_list<int> dispParam;
    forward_list<int>::iterator minI;
    result resParam, minRes;
    vector < tupla_type > alfas;
    alfas.resize(0);
    minRes.peso_total = INT_MAX;
	//cout << "---------------------- \n";
	int peso_aux = INT_MAX;
	int part_aux = 0;
	int alfa;
	int cota;
	int ll;
	forward_list<int>::iterator it_aux;
    int d_size = distance(begin(disponibles), end(disponibles));
    //cout << "entro a particion con " << d_size << " disponibles \n" ;
	for(auto it = disponibles.begin(); it != disponibles.end();++it){
		dispParam = disponibles;
		dispParam.remove(*it);
		it_aux = it;
		
		//no es necesario que obligatoriamente ubique el vertice en una particion nueva
		if (r.p_count > 0 ){
			/*para cada particion creada
			agrego el vertice a la particion y calculo el peso peso_total
			si es mejor que el existente actualizo peso */			
			for(int i=0 ; i< r.p_count; i++){
				//resParam  = r;
				//resParam.particiones[i].push_front(*it);
				//actualizarPeso(resParam,i,*it);
				ll= diferencialPeso(r,i,*it);
				if (ll < peso_aux){
					peso_aux = ll;
					part_aux = i;
					}
				
				/*if (resParam.peso_total < minRes.peso_total){
						minRes = resParam;
						minI = it;
					
				}*/
			}
		}
		
		// si aun se pueden agregar particiones pruebo agregando 
		//una particion
		if ( particionK > r.p_count ){			
			//resParam  = r;
			//resParam.particiones[resParam.p_count].push_front(*it);
			//resParam.p_count += 1;
 			//actualizarPeso(resParam,resParam.p_count-1,*it);
 			ll=diferencialPeso(r,r.p_count,*it);
			
			if (ll < peso_aux){
					peso_aux = ll;
					part_aux = r.p_count;
				}

			/*if (resParam.peso_total < minRes.peso_total){
	//			cout << "actualizo "<< resParam.peso_total << "\n";
				minRes = resParam;				
	//			cout << *it <<" min I \n";
				minI = it;
			}*/
		}
		
		alfas.push_back(make_pair(peso_aux,make_pair(it_aux,part_aux)));
		peso_aux = INT_MAX;
		part_aux = 0;
		
	}

	//al salir del for tengo guardado en el vector para cada nodo donde me  cada uno tengo que escoger un valor aleatoriamente
	make_heap(alfas.begin(),alfas.end(),comp());
	
	tupla_type a;
	/*cout << "a continuacion se imprime el arreglo de alfas" << endl;
 	for (int i=0 ; i < alfas.size(); i++){
		cout << "elemento: " <<i << "del arreglo:" << endl; 
		a = alfas[i];
		cout << "el peso es: " << a.first << " la particion es: " << a.second.second << "  el nodo es " << *a.second.first << endl;
		
	}
	cout << "+++++++++++++++++++++++"<< endl;
	*/
	//el arreglo alfas contiene a las posibles k posiciones de los k nodos (posiciones de peso minimo para cada nodo) de manera ascendente
	alfa = alfas[0].first; //alfa contiene el peso minimo que se va a agregar en esta iteracion
	int alfa2 = alfa;
	cota = (alfa/10);
	cota = cota + alfa;		//para entrar en la lista de candidatos no tienen que superar mas del 25% al candidato optimo
	int j= 0;
	bool cont = true;
	while(alfa2 <= cota && j<alfas.size()){
		//cout << "entre al while" << endl;
		j++;
		alfa2 = alfas[j].first;
		
		//si ya pasaron todos los mejores resultados
		/*if (alfa2 > alfa){
			if(j>4){
			cont = false;
			}
		}*/
		
	}
	//cout << "sali del while" << endl;
	//ahora se escoge un numero aleatorio entre 0 y j
	alfa2 = rand() % j;
	a = alfas[alfa2];
	
	r.particiones[a.second.second].push_front(*a.second.first);
	if (!(r.p_count > a.second.second)){
		r.p_count++;
	}
 	actualizarPeso(r,a.second.second,*a.second.first);
 	
 	//r = minRes;
	//cout << "resultados parciales:" << endl;
	//debugResult(&r);
	if (d_size > 1){
		disponibles.remove(*a.second.first);
	//	cout << "remuevo " << *minI << "\n";
	//	debugResult(&r);		
		particion2(r, disponibles);
	}

}


void grasp2(result  &r, forward_list<int> d){
        //cout << "entro a grasp \n";
        forward_list<int> d1 = d;
        result  raux,best;
       
        int first = 1;
        int bestResult =INT_MAX;
        int resultCount = 0;
        //particion(r,d);
        while (true){          
                //random_shuffle ( shu.begin(), shu.end() );
                //for (int i=0 ; i< shu.size(); i++){
                  //      d1.push_front(shu[i]);
                //}      
                raux = r;
                                
                //cout<< "entro al goloso \n";
                //goloso aleatorizado
                particion2(raux,d1);
                
                //debugResult(&raux);  
                //cout<< "entro al local \n";  
                busquedaLocal(raux);
                //cout<< "salgo del local \n";
                //debugResult(&best);    
                //cout << "test \n" ;
                if ( bestResult  > raux.peso_total){
                        //cout << "aaaa\n";
                        bestResult = raux.peso_total;
                        best =  raux;
                        resultCount = 0;
                }else{
                        //cout << "bbb\n";
                        if (resultCount > 10){
                                break;
                        }else{
                                resultCount ++;
                        }
                }
        }
       //cout << "resultado final:" << endl;
       //debugResult(&best);          
                       

}

//**************************************************************************************************************************


int main(int argc, char** argv) {      
	unsigned long long inicio,total, total2;
    srand ( unsigned ( time(0) ) );
    char line[1000];
    char* strVal;
    int val;
    int readedLine = -1;
    vector <int> instanceTitle(3);
    vector< vector<int> > values;
    int vertices;
    int aristas;	//num total de aristas
    int k,u,v,w;
    int cantNodos, cantAristas, cantConj;
    result r, r2;
    forward_list<int> d, d2;	//lista con todos los vertices
     //unsigned long long contador = 0; 
       
    while ( cin.getline(line, 999, '\n') ) {
        //cout << "while |" << readedLine <<   "| "<< line << "|\n";
        //if (readedLine == 0 and
        if (readedLine == 0) {  

            readedLine -= 1;
            r.p_count = 0;
            r.particiones.resize(particionK);

            for (auto it= r.particiones.begin();it!= r.particiones.end(); ++it){                                                            
					it->clear();                                    
            }                                              
               
            r.peso_total = INT_MAX;                        
            //cout << "\n------------ instancia  --------------\n";
            //cout << "vertices : " << V << " aristas :" << aristas << " k :"<< particionK<< "\n";
            //particion(r,d);
            r2=r;
            d2=d;
            inicio = rdtsc();
            grasp(r,d);
            total = rdtsc() - inicio;
            
            inicio = rdtsc();
            grasp2(r2,d2);
            total2 = rdtsc() - inicio;
            //contador += total;
			//cout << V << " " << aristas << " " << particionK << " "<< total<<endl;        
			cout << cantNodos << " "<< cantAristas << " " << cantConj << " " <<total << " " << total2 <<  endl;  
            //debugResult(&r);            
            //busquedaLocal(r);
            d.resize(0);        
            //printResult(&r);            
            //debugResult(&r);
            //cout << "------ \n";            
            if ( line[0] == '0') break;
        }
        if (readedLine == -1 and line[0] != '0') {                              
            d.resize(0);      
            strVal = strtok(line, " ");
            V = atoi(strVal);			//cant vertices (nodos)
            cantNodos = V;

            strVal = strtok(NULL, " ");
            aristas = atoi(strVal);		//cant aristas (ejes)
            cantAristas=aristas; 

            strVal = strtok(NULL, " ");
            particionK = atoi(strVal);	//parametro num de conj
            cantConj = particionK; 

            readedLine = aristas;
            //grafoAdj.resize(0 ) ;
            grafoAdj.resize(V);
            for (int i=0; i<V ; i++){
				grafoAdj[i].resize(V,0);		//matriz de adyacencias
            }
            
            for (int i=0; i<V ; i++){
				d.push_front(i);		//guarda en "d" los nodos de forma descendente
            }
        } else {		//
            strVal = strtok(line, " ");
            u = atoi(strVal);	

            strVal = strtok(NULL, " ");
            v = atoi(strVal);

            strVal = strtok(NULL, " ");
            w = atoi(strVal);
            putEje(u,v,w);  
            readedLine -= 1;            
        }
    }
    //contador = (contador/100);
	//cout << contador <<endl;  
    return 0;
}

